public class code02 {
//    力扣 150 二叉树的锯齿形层序遍历
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    // 这道题目的要求是要实现一轮正序一轮逆序的情况来遍历二叉树
    // 在最基础的层序遍历中，我们使用的是 队列 来实现的
    // 在这里要考虑到顺序，我们就可以采用 双端队列 来尝试解决问题
    if(root == null) {
        return new ArrayList<>();
    }

    // 首先定义一个符合返回条件的顺序表
    List<List<Integer>> re = new LinkedList<>();

    // 在来定义一个队列来存储其中的节点信息
    // 这里使用最普通的队列就行
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    // 定义一个 boolean 类型的标志位，用来确定当前行的遍历规则
    boolean flag = true;

    // 使用迭代来完成题目要求
    while(!queue.isEmpty()) {
        // 在这里定义出一个双端队列
        Deque<Integer> deq = new LinkedList<>();

        // 获取到 queue 中的元素个数，将这些元素存储到双端队列中
        int size = queue.size();

        for(int i = 0; i < size; i++) {

            TreeNode node = queue.poll();

            // 根据标志位，选择本层的数据存储顺序
            if(flag) {
                // 先从右向左
                deq.offerLast(node.val);
            } else {
                deq.offerFirst(node.val);
            }

            // 判断存储结束后，需要更新当前节点的左右子节点到 queue 中
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }

        // 当一次 for 循环结束后，此时就表明当前层已经变了结束
        // 首先更改一下标志位
        flag = !flag;
        // 在来将当前层的遍历结果存储起来
        List<Integer> s = new LinkedList<Integer>(deq);
        re.add(s);
    }

    // 最终返回链表
    return re;
}
}
